package chapter01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Permute46 {
    /**
     * 回溯法
     * [pos...] 从pos位置到length-1的全排列
     * 递归出口
     *      pos==length-1
     *      后续不需要在进行全排列
     *  当前来到pos位置 [... pos i j l k l m n ...]
     *  pos位置可以是[pos]~[length-1]中一个 确定了pos位置那么我们只需求[pos+1...]的全排列即可
     *  pos位置有多种选择 在一次选择结束即将进入第二次选择时 需要将上一次选择恢复成原来状态
     *  比如[... i pos j l k l m n ...] pos位置与[i]交换
     *      在进入pos位置与[j]交换前 需要将上一次pos位置恢复原样[... pos i j l k l m n ...]
     *      这样在回到递归中时 我们交换的才是[pos]与[j] 不然交换的就是[i]与[j]
     *     [... j i pos l k l m n ...]  pos位置与[j]交换
     */
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> path=new ArrayList<Integer>();
        for(int num:nums){
            path.add(num);
        }
        dfs(nums,0,path);
        return list;
    }

    public void dfs(int[] nums,int pos,List<Integer> path){
        if(pos==nums.length-1){
            list.add(new ArrayList<>(path));
            return;
        }
        for(int i=pos;i<nums.length;i++){
            Collections.swap(path,pos,i);
            dfs(nums,pos+1,path);
            Collections.swap(path,pos,i);
        }
    }

}
